#include <iostream>
#include <stack>
#include <vector>
#include <unordered_set>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

vector<int> postorderTraversal(TreeNode* root) {
    vector<int> ans;
    if(!root) return ans;
    stack<TreeNode*> st;
    unordered_set<TreeNode*> visited;
    st.push(root);
    while(!st.empty()){
        TreeNode* l = st.top()->left;
        TreeNode* r = st.top()->right;
        if(r && !visited.count(r)) st.push(r);
        if(l && !visited.count(l)) st.push(l);
        if((!r || visited.count(r)) && (!l || visited.count(l))){
            ans.push_back(st.top()->val);
            visited.insert(st.top());
            st.pop();
        }
    }
    return ans;
}